A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.     

The snowblower problem

We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile.We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded-capacity dust bin.     

A note on “A LP-based heuristic for a time-constrained routing problem”

In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.     

Green synthesis of new thiouracilodepsipeptides in ionic liquid: One‐pot four‐component reaction of isocyanides

Thiouracil‐containing depsipeptides were produced via one‐pot four‐component condensation/Passerini tandem reaction of thiouracil, 2‐chloroacetic acid derivatives, ketones, and isocyanides in ionic liquid as green reaction media in high yields.     

Oxidative ring-opening of isatins for the synthesis of 2-aminobenzamides and 2-aminobenzoates

An efficient and practical isatin-based oxidative domino protocol has been developed for the facile synthesis of 2-aminobenzamides and 2-aminobenzoates. The robust nature of this reaction system is reflected by accessible starting materials, room temperature and high-yield gram-scale synthesis.     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

基于无线Mesh网络的一种信道分配算法及路由协议

提出了在多信道环境下的无线Mesh网络中的一种混合型路由协议TOIRP(tree-based and on-de-mand integrated routing protocol)以及一种分布式的信道分配算法CLBCA(channel load based channel assign-ment).TOIRP协议采用HWMP(hybrid wireless mesh protocol)所提出的混合路由技术,将基于树的路由与传统的AODV(ad hoc on-demand distance vector)路由相结合,减少路由发现的时延,同时采用了一种新的路由判据CETTI(cumulative expected transmission time with interference).该路由判据充分考虑多信道的特性,设计了一种量化通信干扰的方法,将干扰分为外部数据流对路径的干扰以及路径内部数据流的干扰两个方面,并综合考虑了跳数、时延等因素,提高了网络的吞吐量.信道分配算法分为收发器与邻居节点绑定和收发器与信道绑定两个部分,将信道的负载作为选择信道的标准,避免了多信道中常见的信道依赖所造成的影响,并且提高了信道的利用率.模拟结果表明,采用新的路由判据后,网络的吞吐量最优情况下得到提升.     

Adaptive local routing strategy on a scale-free network

Due to the heterogeneity of the structure on a scale-free network, making the betweennesses of all nodes become homogeneous by reassigning the weights of nodes or edges is very difficult. In order to take advantage of the important effect of high degree nodes on the shortest path communication and preferentially deliver packets by them to increase the probability to destination, an adaptive local routing strategy on a scale-free network is proposed, in which the node adjusts the forwarding probability with the dynamical traffic load (packet queue length) and the degree distribution of neighbouring nodes. The critical queue length of a node is set to be proportional to its degree, and the node with high degree has a larger critical queue length to store and forward more packets. When the queue length of a high degree node is shorter than its critical queue length, it has a higher probability to forward packets. After higher degree nodes are saturated (whose queue lengths are longer than their critical queue lengths), more packets will be delivered by the lower degree nodes around them. The adaptive local routing strategy increases the probability of a packet finding its destination quickly, and improves the transmission capacity on the scale-free network by reducing routing hops. The simulation results show that the transmission capacity of the adaptive local routing strategy is larger than that of three previous local routing strategies.     

WDM光网络呼叫阻塞性能分析

基于波长路由的WDM光网络L跳路径独立模型,研究节点无波长转换功能的光通路呼叫请求过程,提出了阻塞性能的数学分析方法．模型中引入了光网络资源所应该考虑的光节点接收器的配置情况．数值分析表明：光纤中复用的波长数越多以及网络通信负载量较小时,配置光节点接收器能明显改善光网络的阻塞性能．     

一种高生存性的车载自组网可信路由协议

针对目前车载自组网中路由安全问题,提出一种基于经验信任的可信路由模型.该模型从客观信任的角度引入经验信任的概念作为可信度量的标准,并给出了计算节点经验信任值和信誉度的推荐方法,根据节点的经验信任值设计一种新的动态包转发规则,从而实现车载自组网的可信路由.实验结果表明,该模型较贪婪周边无状态路由(greedy perimeter stateless routing,GPSR)协议具有较高的抵抗自私节点的能力.